#define  _CRT_SECURE_NO_WARNINGS
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */

 // 1.1:
 // class Solution {
 // public:
 //     ListNode* mergeKLists(vector<ListNode*>& lists) {
 //         ListNode guard, *tail = &guard;
 //         for(int i = 0; i < lists.size(); i++)
 //         {
 //             ListNode* cur1 = guard.next, *cur2 = lists[i];
 //             if(!cur2)continue;
 //             guard.next = nullptr;
 //             tail = &guard;
 //             while(cur1 && cur2)
 //             {
 //                 if(cur1->val < cur2->val)
 //                 {
 //                     tail->next = cur1;
 //                     cur1 = cur1->next;
 //                 }
 //                 else
 //                 {
 //                     tail->next = cur2;
 //                     cur2 = cur2->next;
 //                 }
 //                 tail = tail->next;
 //             }
 //             if(cur1) tail->next = cur1;
 //             if(cur2) tail->next = cur2;
 //         }
 //         return guard.next;
 //     }
 // };
 // 1.2:
 // class Solution {
 // public:
 //     ListNode* mergeKLists(vector<ListNode*>& lists) {
 //         if(lists.size() == 0)return 0;
 //         ListNode guard, *tail = &guard;
 //         tail->next = lists[0];
 //         for(int i = 1; i < lists.size(); i++)
 //         {
 //             ListNode* cur1 = guard.next, *cur2 = lists[i];
 //             if(!cur2)continue;
 //             guard.next = nullptr;
 //             tail = &guard;
 //             while(cur1 && cur2)
 //             {
 //                 if(cur1->val < cur2->val)
 //                 {
 //                     tail->next = cur1;
 //                     cur1 = cur1->next;
 //                 }
 //                 else
 //                 {
 //                     tail->next = cur2;
 //                     cur2 = cur2->next;
 //                 }
 //                 tail = tail->next;
 //             }
 //             if(cur1) tail->next = cur1;
 //             if(cur2) tail->next = cur2;
 //         }
 //         return guard.next;
 //     }
 // };

 // 2:
 // class Solution {
 //     struct cmp
 //     {
 //         bool operator()(ListNode* n1, ListNode* n2)
 //         {
 //             return n1->val > n2->val;
 //         }
 //     };
 // public:
 //     ListNode* mergeKLists(vector<ListNode*>& lists) {
 //         ListNode guard, *tail = &guard;
 //         priority_queue<ListNode*,vector<ListNode*>,cmp> pq;
 //         for(int i = 0; i < lists.size(); i++)
 //         {
 //             ListNode* cur = lists[i];
 //             while(cur)
 //             {
 //                 ListNode* next = cur->next;
 //                 cur->next = nullptr;
 //                 pq.push(cur);
 //                 cur = next;
 //             }
 //         }
 //         while(!pq.empty())
 //         {
 //             tail->next = pq.top();
 //             tail = tail->next;
 //             pq.pop();
 //         }
 //         return guard.next;
 //     }
 // };

  // 3:
  class Solution {
      ListNode* mergeSort(vector<ListNode*>& lists, int left, int right)
      {
          if(left >= right) return lists[left];
          int mid = (left + right) >> 1;
          ListNode* cur1 = mergeSort(lists, left, mid);
          ListNode* cur2 = mergeSort(lists, mid + 1, right);
          ListNode guard, *tail = &guard;
          while(cur1 && cur2)
          {
              if(cur1->val < cur2->val)
              {
                  tail->next = cur1;
                  cur1 = cur1->next;
              }
              else
              {
                  tail->next = cur2;
                  cur2 = cur2->next;
              }
              tail = tail->next;
          }
          if(cur1) tail->next = cur1;
          if(cur2) tail->next = cur2;
          return guard.next;
      }
  public:
      ListNode* mergeKLists(vector<ListNode*>& lists) {
          if(lists.size() == 0)return 0;
          return mergeSort(lists, 0, lists.size() - 1);
      }
  };